A tree is a data structure that is an acyclic connected graph where the nodes of the graph each have zero or more children nodes and at most one parent node. FIG. 1 illustrates a tree data structure that depicts the relationships between the nodes of the tree data structure in accordance with the prior art. A node is a basic unit of a data structure that may contain a value, a condition, or represent a separate data structure. In a tree data structure, each node has zero or more child nodes, which are below it in the tree. By convention, as shown in FIG. 1, trees are depicted growing downwards.
Searching a tree data structure is done several different ways, in which most searches will include a tree traversal, which is the process of visiting (examining and/or updating) each node in a tree data structure, exactly once, in a systematic way. When traversing a tree, a search returns a desired value by extracting it from a node of the tree. Such an extraction will often include a reference to the particular location of the node as well. The location can be identified explicitly or relative to other nodes. Where the node is identified relative to another node, the distances between nodes can be measured in steps, where one step is basically a direct link between a child node and its parent. For example, in FIG. 1, walking from node “A” to “E” is two steps, and walking from “D” to “E” is two steps. Walking from node “D” to “C” is three steps, which includes two upwards steps from “D” to “A” and one downward step from “A” to “C”. To illustrate this point further, the distance between “E” and “F” is four steps. Note that a step is in a downward or upward direction.
Because of the nature of a tree data structure it is not out of the ordinary in a search to find the same searched value at several nodes in the tree. It is also possible for such nodes to be the same distance from the node initiating the search, in which the nodes will have the same relative locations.
This creates ambiguity and decreases the effectiveness of the search. That is, ambiguity occurs in a search of a tree when the same values occur at different nodes of a tree. Ambiguity may be resolved by comparing the distance of walking through a tree to get from the node that the search is initiated (i.e. the context node) to the nodes that contain the searched value (i.e. the candidate nodes). The distance is measured in units of steps, where one step is one edge between a child node and its parent, whether that step is upward or downward. Such occurrences are distinguishable when they occur at various distances from the context node. This is not the case when occurrences are the same number of steps from the context node. If only one instance of the value is desired in a search of a tree, a method must be employed to determine which instance to return. A technique is desired for eliminating this ambiguity in the search results.